import java.util.*;

public class HNMap<K, V> extends AbstractMap<K, V> implements Map<K, V> {


    HNode<K, V>[] table;
    Set<Map.Entry<K, V>> entrySet;
    int size;
    int threshold;
    final float loadFactor;


    final int INIT_CAPACITY = 16;
    final int MAX_CAPACITY = Integer.MAX_VALUE;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    final int TO_TREE = 8;
    final int TO_LINK = 6;

    class HNode<K, V> implements Map.Entry<K, V> {
        final int hash;
        final K key;
        V value;
        HNode<K, V> nextNode;

        public HNode(int hash, K key, V value, HNode<K, V> nextNode) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.nextNode = nextNode;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }

        // 返回的是旧值
        @Override
        public V setValue(V value) {
            V old = this.value;
            this.value = value;
            return old;
        }
    }

    public HNMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }

    public HNMap(int initCapacity) {
        this(initCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HNMap(int initCapacity, float loadFactor) {
        this.threshold = (int) (initCapacity * loadFactor);
        this.loadFactor = loadFactor;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public V get(Object key) {
        HNode<K, V> result = getNode(hash(key), key);
        if (result == null)
            return null;
        return result.value;
    }

    HNode<K, V> getNode(int hash, Object key) {
        HNode<K, V>[] tab = table;
        if (tab == null || tab.length == 0) {
            return null;
        }
        int length = tab.length;
        HNode<K, V> first, result;
        first = tab[(length - 1) & hash];
        if (first == null) {
            return null;
        }
        if (first.hash == hash && (first.key == key || (key != null && key.equals(first.key)))) {
            return first;
        }
        result = first.nextNode;
        if (result != null) {
            do {
                if (result.hash == hash && (result.key == key || (key != null && key.equals(result.key)))) {
                    return result;
                }
                result = result.nextNode;
            } while (result != null);
        }
        return null;
    }

    int hash(Object key) {
        int h;
        if (key == null)
            return 0;
        h = key.hashCode();
        return h ^ (h >>> 16);
    }


    public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }

    public V put(K key, V value) {
        return putValue(hash(key), key, value, false);
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        return null;
    }

    V putValue(int hash, K key, V value, boolean ifAbsent) {
        HNode<K, V>[] tab = table;
        HNode<K, V> target;
        int length = 0, index;
        if (tab == null || tab.length == 0) {
            tab = resize();
            length = tab.length;
        }
        index = (length - 1) & hash;
        target = tab[index];
        if (target == null) {
            tab[index] = newNode(hash, key, value, null);
        } else {
            HNode<K, V> nowNode = null;
            if (target.hash == hash &&
                    (target.key == key || (key != null && key.equals(target.key)))) {
                nowNode = target;
            } else {
                int count = 0;
                while (true) {
                    nowNode = target.nextNode;
                    if (nowNode == null) {
                        target.nextNode = newNode(hash, key, value, null);
                        break;
                    }
                    if (nowNode.hash == hash && (nowNode.key == key || (key != null && key.equals(nowNode.key)))) {
                        break;
                    }
                    target = nowNode;
                }
            }
            if (nowNode != null) {
                V oldValue = nowNode.value;
                if (!ifAbsent || oldValue == null) {
                    nowNode.value = value;
                }
                return oldValue;
            }
        }
        if (++size > threshold) {
            resize();
        }
        return null;
    }

    HNode<K, V> newNode(int hash, K key, V value, HNode<K, V> next) {
        return new HNode<>(hash, key, value, next);
    }

    HNode<K, V>[] resize() {
        HNode<K, V>[] oldTab = table;
        int oldCapacity = 0;
        int oldThreshold = threshold;
        int newCapacity;
        int newThreshold = 0;
        if (oldTab != null) {
            oldCapacity = oldTab.length;
        }
        if (oldCapacity > 0) {
            if (oldCapacity >= MAX_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            newCapacity = oldCapacity << 1;
            if (newCapacity < MAX_CAPACITY) {
                newThreshold = oldThreshold << 1;
            }
        } else if (oldThreshold > 0) {
            newCapacity = oldThreshold;
        } else {
            newCapacity = INIT_CAPACITY;
            newThreshold = (int) (DEFAULT_LOAD_FACTOR * INIT_CAPACITY);
        }
        if (newThreshold == 0) {
            float newTh = (float) newCapacity * loadFactor;
            if (newCapacity < MAX_CAPACITY && newTh < (float) MAX_CAPACITY) {
                newThreshold = (int) newTh;
            } else {
                newThreshold = Integer.MAX_VALUE;
            }
        }
        threshold = newThreshold;
        HNode<K, V>[] newTab = (HNode<K, V>[]) new HNode[newCapacity];
        table = newTab;
        if (oldTab != null) {
            // TODO: 2022-04-26 reHash
        }
        return table;
    }

    public V remove(Object key) {
        HNode<K, V> target = removeNode(hash(key), key, null, false);
        if (target == null)
            return null;
        return target.value;
    }

    /*
        matchValue:当值相等的时候才移除
     */
    HNode<K, V> removeNode(int hash, Object key, Object value, boolean matchValue) {
        HNode<K, V>[] tab = table;
        HNode<K, V> target;
        int length, index;
        if (tab == null || tab.length == 0) {
            return null;
        }
        length = tab.length;
        index = (length - 1) & hash;
        target = tab[index];
        if (target == null) {
            return null;
        }
        // 需要被删除的Node
        HNode<K, V> nowNode = null;
        HNode<K, V> deepNode;
        if (target.hash == hash && (target.key == key || (key != null && key.equals(target.key)))) {
            nowNode = target;
        } else if (target.nextNode != null) {
            deepNode = target.nextNode;
            do {
                if (deepNode.hash == hash && (deepNode.key == key || (key != null && key.equals(deepNode.key)))) {
                    nowNode = deepNode;
                    break;
                }
                target = deepNode;
                deepNode = deepNode.nextNode;
            }
            while (deepNode != null);
        }
        if (nowNode != null && (!matchValue || nowNode.value == value || (value != null && value.equals(nowNode.value)))) {
            if (nowNode == target) {
                tab[index] = nowNode.nextNode;
            } else {
                target.nextNode = nowNode.nextNode;
            }
            size--;
            return nowNode;
        }
        return null;
    }

    public void clear() {
        HNode<K, V>[] tab = table;
        if (tab == null || tab.length == 0) {
            return;
        }
        size = 0;
        Arrays.fill(tab, null);
    }

    @Override
    public V getOrDefault(Object key, V defaultValue) {
        HNode<K, V> target = getNode(hash(key), key);
        if (target == null) {
            return defaultValue;
        }
        return target.value;
    }

    @Override
    public V putIfAbsent(K key, V value) {
        return putValue(hash(key), key, value, true);
    }

    @Override
    public boolean remove(Object key, Object value) {
        return removeNode(hash(key), key, value, true) != null;
    }

    @Override
    public boolean replace(K key, V oldValue, V newValue) {
        HNode<K, V> target = getNode(hash(key), key);
        if (target == null || target.value != oldValue) {
            return false;
        }
        target.value = newValue;
        return true;
    }

    @Override
    public V replace(K key, V value) {
        HNode<K, V> target = getNode(hash(key), key);
        if (target == null) {
            return null;
        }
        V oldValue = target.value;
        target.value = value;
        return oldValue;
    }
}
